🌓

ds 随笔

创建于 2023-09-26

ds 随笔

不定时更新喏。

代码中可能没附加 #define int long long。

本文仅是记录一些 $\text{ds}$ 题做题记录，质量低下。

Luogu P7214 [JOISC2020] 治療計画

Luogu P9388 [THUPC 2023 决赛] 先人类的人类选别

CF1591F Non-equal Neighbours

Luogu P6237 [CEOI2012] Printed Circuit Board

Luogu P3760 [TJOI2017] 异或和

Luogu P5319 [BJOI2019] 奥术神杖

CF283E Cow Tennis Tournament

Luogu P5327 [ZJOI2019] 语言

Luogu P7603 [THUPC2021] 鬼街

CF1336F Journey

AT_dp_w Intervals

Luogu P6617 查找 Search

CF702F T-Shirts

Luogu P8421 [THUPC2022 决赛] rsraogps

CF878D Magic Breeding

CF605D Board Game

CF372D Choosing Subtree is Fun

Luogu P5685 [JSOI2013] 快乐的 JYY

Luogu P4192 旅行规划

上面这个目录不舒适了，改一下：（ $\text{update:}9.26$ ）

AT_cf17_final_j Tree MST

CF715C Digit Tree

Luogu P8991 北大集训 2021 出题高手

Luogu P3765 总统选举

CF700D Huffman Coding on Segment

CF1553H XOR and Distance

CF1140G Double Tree

CF1149C Tree Generator™

CF487E Tourists

CF875E Delivery Club

CF1017H The Films

Luogu P5381 [THUPC2019] 不等式

Luogu P5443 [APIO2019] 桥梁

CF713D Animals and Puzzle

Luogu P9607 [CERC2019] Be Geeks!

JOISC2016 回転寿司

Luogu P7482 不条理狂诗曲

Luogu P4340 SHOI2016 随机序列

Luogu P7826 「RdOI R3」RBT

CF1083C Max Mex

Luogu P9531 JOISC2022 复兴计划

Luogu P7214 [JOISC2020] 治療計画

个人认为挺有意思的最短路题。

我们要全部治疗，意味着肯定要有选中 $[1, x]$ 和 $[y, n]$ 状物。

你考虑我们把所有形如 $[1, x]$ 的治疗当作起点， $[y, n]$ 的治疗当作终点。

我们发现最后的目的是一路将方案拼接过去使得 $[1, n]$ 可以全部治疗。

两个治疗方案有边仅当两个治疗方案能拼接，这里拼接并不是指有交，即若 $|T_i - T_j| \le R_i - L_j + 1$ ，则连 $(i, j)$ 有向边。

这样送起点到终点的路径的意义就是能将方案拼接出一个 $[1, n]$ 的区间，直接跑点权最短路。

这个点权最短路有每个点只会松弛一次的特殊性质，直接 $\text{BIT}$ 维护松弛过程即可。

时间复杂度 $O(m \log m)$

code

const int N = 1e5 + 10;
ll L[N], R[N], T[N], dis[N], tab[N], c[N];
int g[N], len, n, m, id[N];
inline ll val1(int x) { return T[x] - L[x]; }
inline ll val2(int x) { return -T[x] - L[x]; }
vector<int> T1[N], T2[N];
inline void ins1(int u, int v) {
    while (u <= len) T1[u].push_back(v), u += u & -u; 
}
inline void ins2(int u, int v) {
    while (u) T2[u].push_back(v), u -= u & -u;
}
priority_queue<pair<ll, int> > q;
inline void upd(int x, ll v) {
    if (v < dis[x]) dis[x] = v, q.emplace(-dis[x], x);
}
inline void modify1(int u, ll v, ll d) {
    while (u) {
        while (T1[u].size() && val1(T1[u].back()) >= v)
            upd(T1[u].back(), d + c[T1[u].back()]), T1[u].pop_back();
        u -= u & -u;
    }
}
inline void modify2(int u, ll v, ll d) {
    while (u <= len) {
        while (T2[u].size() && val2(T2[u].back()) >= v)
            upd(T2[u].back(), d + c[T2[u].back()]), T2[u].pop_back();
        u += u & -u;
    }
}
int main() {
    read(n, m);
    for (int i = 1; i <= m; i++) id[i] = i;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= m; i++) {
        read(T[i], L[i], R[i], c[i]), tab[i] = T[i];
        if (L[i] == 1) dis[i] = c[i], q.emplace(-c[i], i);
    }
    sort(tab + 1, tab + m + 1), len = unique(tab + 1, tab + m + 1) - tab - 1;
    for (int i = 1; i <= m; i++) g[i] = lower_bound(tab + 1, tab + len + 1, T[i]) - tab;
    sort(id + 1, id + m + 1, [&](int x, int y) { return val1(x) < val1(y); });
    for (int i = 1; i <= m; i++) ins1(g[id[i]], id[i]);
    sort(id + 1, id + m + 1, [&](int x, int y) { return val2(x) < val2(y); });
    for (int i = 1; i <= m; i++) ins2(g[id[i]], id[i]);
    while (q.size()) {
        int u = q.top().second;
        q.pop(), modify1(g[u], T[u] - R[u] - 1, dis[u]), modify2(g[u], -T[u] - R[u] - 1, dis[u]);
    }
    ll ans = INF;
    for (int i = 1; i <= m; i++)
        if (R[i] == n) chkmin(ans, dis[i]);
    cout << (ans == INF ? -1 : ans);
    return 0;
}

Luogu P9388 [THUPC 2023 决赛] 先人类的人类选别

前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和前缀和。

将询问差分后查询前缀和，我们发现前 $x$ 个数保留的数就是这 $x$ 个数并上操作的所有数的前 $x$ 大的数，直接权值主席树。

时间复杂度 $O((n + m) \log n)$

code

const int N = 5e5 + 10;
int n, m;
int lc[N * 20], pos[N], rc[N * 20], tot, a[N * 20], b[N << 2], v[N], root[N];
ll suma[N * 20], sumb[N * 20];
void update(int &u, int lu, int L, int R, int x) {
    u = ++tot, lc[u] = lc[lu], rc[u] = rc[lu], a[u] = a[lu] + 1,
    suma[u] = suma[lu] + x;
    if (L == R) return;
    int M = L + R >> 1;
    if (x <= M) return update(lc[u], lc[lu], L, M, x);
    return update(rc[u], rc[lu], M + 1, R, x);
}
void build(int u, int L, int R) {
    if (L == R) return pos[L] = u, void();
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R);
}
inline void update(int x, int v) {
    x = pos[x], ++b[x], sumb[x] += v;
    while (x >>= 1) ++b[x], sumb[x] += v;
}
ll query(int u, int v, int L, int R, int x, ll w = 0) {
    if (L == R) return 1ll * x * L + w;
    int M = L + R >> 1;
    if (x > b[v << 1 | 1] + a[rc[u]]) return query(lc[u], v << 1, L, M, x - b[v << 1 | 1] - a[rc[u]], suma[rc[u]] + sumb[v << 1 | 1] + w);
    return query(rc[u], v << 1 | 1, M + 1, R, x, w);
}
inline ll calc(int x) {
    if (!x) return 0;
    return query(root[x], 1, 1, n, x);
}
int main() {
    read(n, m);
    for (int i = 1; i <= n; i++)
        read(v[i]), update(root[i], root[i - 1], 1, n, v[i]);
    build(1, 1, n);
    while (m--) {
        int x, l, r;
        read(x, l, r), update(x, x);
        println(calc(r) - calc(l - 1));
    }
    return 0;
}

CF1591F Non-equal Neighbours

垃圾题，线段树优化 $\text{dp}$ 即可。

Luogu P6237 [CEOI2012] Printed Circuit Board

李超 $2 \log$ ，旋转扫描线 $1\log$ ，板子题而已。

Luogu P3760 [TJOI2017] 异或和

存在 $1 \log$ 做法，但我不会。

拆位后考虑 $a - b$ 的第 $x$ 位为 $1$ 当前仅当 $a, b$ 的 $x$ 位不同且没有借位或是相同且有借位。

借位的意义是 $x$ 及之后的位的大小关系，直接做即可，复杂度双 $\log$ 。

code

const int N = 1e6 + 10;
struct BIT {
    int w[N], V = 1e6 + 1;
    int sum = 0;
    inline void update(int u) {
        ++u, sum ^= 1;
        while (u <= V) w[u] ^= 1, u += u & -u;
    }
    inline int query(int u) {
        ++u;
        int ans = 0;
        while (u) ans ^= w[u], u ^= u & -u;
        return ans;
    }
    inline void clr() { memset(w, 0, sizeof(w)), sum = 0; }
} a, b;
int n, x[N], s[N];
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(x[i]), s[i] = s[i - 1] + x[i];
    ll ans = 0;
    for (int i = 0; i <= 21; i++) {
        a.clr(), b.clr();
        int res = 0;
        for (int j = 0; j <= n; j++) {
            ll p = s[j] & ((1 << i) - 1);
            if (s[j] & (1 << i)) {
                res ^= b.query(p), res ^= a.sum ^ a.query(p);
                a.update(p);
            } else {
                res ^= a.query(p), res ^= b.sum ^ b.query(p);
                b.update(p);
            }
        }
        if (res) ans |= 1ll << i;
    }
    cout << ans;
    return 0;
}

Luogu P5319 [BJOI2019] 奥术神杖

取 $\ln$ 后直接二分 $+$ $\text{dp on ACAM}$ 即可。

CF283E Cow Tennis Tournament

算不合法。

code

const int N = 2e5 + 10;
int w1[N << 2], w2[N << 2], tag[N << 2];
#define maketag(u) swap(w1[u], w2[u]), tag[u] ^= 1
#define pushup(u) \
    w1[u] = w1[u << 1] + w1[u << 1 | 1], w2[u] = w2[u << 1] + w2[u << 1 | 1]
inline void pushdown(int u) {
    if (tag[u]) maketag(u << 1), maketag(u << 1 | 1), tag[u] ^= 1;
}
void addtag(int u, int L, int R, int l, int r) {
    if (L >= l && R <= r) return maketag(u), void();
    if (L > r || R < l) return;
    int M = L + R >> 1;
    pushdown(u);
    addtag(u << 1, L, M, l, r), addtag(u << 1 | 1, M + 1, R, l, r);
    pushup(u);
}
void build(int u, int L, int R) {
    if (L == R) return void(w1[u] = R - L + 1);
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R), pushup(u);
}
inline int query(int u, int L, int R, int x) {
    if (L == R) return w1[u];
    pushdown(u);
    int M = L + R >> 1;
    if (x <= M) return query(u << 1, L, M, x);
    return query(u << 1 | 1, M + 1, R, x);
}
int n, k;
ll ans;
int a[N];
vector<pair<int, int> > vec[N];
int main() {
    read(n, k), ans = 1ll * n * (n - 1) * (n - 2) / 6;
    for (int i = 1; i <= n; i++) read(a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1, l, r; i <= k; i++) {
        read(l, r), l = lower_bound(a + 1, a + n + 1, l) - a, r = upper_bound(a + 1, a + n + 1, r) - a - 1;
        vec[l].emplace_back(l, r), vec[r + 1].emplace_back(l, r);
    }
    for (int i = 1; i <= n; i++) vec[i].emplace_back(i, i);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        for (auto [l, r] : vec[i]) addtag(1, 1, n, l, r);
        ll cnt = w1[1] - query(1, 1, n, i);
        ans = ans - 1ll * cnt * (cnt - 1) / 2;
    }
    cout << ans;
    return 0;
}

P5327 [ZJOI2019] 语言

可以转化至每个点有一个虚树，初始只有自己，执行链上虚树加点操作，查询最后每个点的虚树的斯坦纳树大小， $\text{dfn}$ 排序后直接做即可。

code

namespace MYEE_TRIE {
typedef long long llt;
typedef unsigned uint;
typedef unsigned long long ullt;
typedef bool bol;
typedef char chr;
typedef void voi;
typedef double dbl;
template <typename T>
bol _max(T &a, T b) {
    return (a < b) ? a = b, true : false;
}
template <typename T>
bol _min(T &a, T b) {
    return (b < a) ? a = b, true : false;
}
template <typename T>
T power(T base, T index, T mod) {
    return ((index <= 1) ? (index ? base : 1)
                         : (power(base * base % mod, index >> 1, mod) *
                            power(base, index & 1, mod))) %
           mod;
}
template <typename T>
T lowbit(T n) {
    return n & -n;
}
template <typename T>
T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <typename T>
T lcm(T a, T b) {
    return (a != 0 || b != 0) ? a / gcd(a, b) * b : (T)0;
}
template <typename T>
T exgcd(T a, T b, T &x, T &y) {
    if (!b) return y = 0, x = 1, a;
    T ans = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ans;
}
const uint Dep = 4, W = 64, LogW = 6, And = W - 1, Val = 16777216 >> 6;
ullt BUFF[Val >> LogW << 1 | 1];
ullt *BT = BUFF + sizeof(BUFF) / sizeof(ullt);
ullt *NewMemory(uint siz) { return BT -= siz; }
inline uint hp(ullt v) { return W - __builtin_clzll(v) - 1; }
inline uint lp(ullt v) { return __builtin_ctzll(v); }
struct Trie {
    ullt *Node[Dep - 1];
    Trie() {
        for (uint i = 0; i + 1 < Dep; i++)
            Node[i] = NewMemory(1llu << (LogW * i));
    }
    inline voi insert(uint v) {
        for (uint i = Dep - 2; ~i; i--) {
            if (Node[i][v >> LogW] >> (v & And) & 1) return;
            Node[i][v >> LogW] |= 1llu << (v & And), v >>= LogW;
        }
    }
    inline voi erase(uint v) {
        if (!(Node[Dep - 2][v >> LogW] >> (v & And) & 1)) return;
        for (uint i = Dep - 2; ~i; i--) {
            Node[i][v >> LogW] &= ~(1llu << (v & And)), v >>= LogW;
            if (Node[i][v]) return;
        }
    }
    inline uint pre(uint v) {
        for (uint i = Dep - 2; ~i; i--, v >>= LogW)
            if (Node[i][v >> LogW] & ~((-1llu) << (v & And))) {
                uint p = hp(Node[i][v >> LogW] & ~((-1llu) << (v & And))) |
                         (v >> LogW << LogW);
                while (++i <= Dep - 2) p = (p << LogW) | hp(Node[i][p]);
                return p;
            }
        return 0;
    }
    inline uint suf(uint v) {
        // cout << "find:" << v << endl;
        for (uint i = Dep - 2; ~i; i--, v >>= LogW)
            if (Node[i][v >> LogW] & ((-1llu) << (v & And) << 1)) {
                uint p = lp(Node[i][v >> LogW] & ((-1llu) << (v & And) << 1)) |
                         (v >> LogW << LogW);
                while (++i <= Dep - 2) p = (p << LogW) | lp(Node[i][p]);
                return p;
            }
        return 0;
    }
} T;
};  // namespace MYEE_TRIE
using MYEE_TRIE::T;
const int N = 1e5 + 10;
int dfn[N], fa[N], id[N], top[N], siz[N], son[N], n, m, dfncnt;
long long dep[N];
struct Edge {
    int next, v;
} edge[N << 1];
int h[N], cnt;
inline void addedge(int u, int v) { edge[++cnt] = {h[u], v}, h[u] = cnt; }
struct Point {
    int x;
    inline bool operator<(const Point b) const { return dfn[x] < dfn[b.x]; }
};
void dfs(int u) {
    siz[u] = 1;
    for (int i = h[u], v; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == fa[u]) continue;
        fa[v] = u, dep[v] = dep[u] + 1, dfs(v), siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u) {
    id[dfn[u] = ++dfncnt] = u;
    if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
    for (int i = h[u], v; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == fa[u] || v == son[u]) continue;
        fa[v] = u, top[v] = v, dfs2(v);
    }
}
inline int lca(int u, int v) {
    while (top[u] != top[v])
        dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
long long ans = 0;
inline long long dis(int u, int v) {
    return dep[u] + dep[v] - (dep[lca(u, v)] << 1);
}
namespace trivial_tree {
int vis[N];
inline void add(int x, int v) {
    if (!vis[x]) {
        int qt = T.suf(0);
        if (qt) {
            int x1, x2;
            int c = T.suf(dfn[x]);
            if (!c)
                x1 = qt;
            else
                x1 = c;
            if (c == qt || !c)
                x2 = T.pre(n + 1);
            else
                x2 = T.pre(c);
            ans += dis(id[x1], x) + dis(x, id[x2]) - dis(id[x1], id[x2]);
        }
        T.insert(dfn[x]);
    }
    vis[x] += v;
}
inline void del(int x, int v) {
    if (!(vis[x] -= v)) {
        T.erase(dfn[x]);
        int qt = T.suf(0);
        if (qt) {
            int x1, x2;
            int c = T.suf(dfn[x]);
            if (!c)
                x1 = qt;
            else
                x1 = c;
            if (c == qt || !c)
                x2 = T.pre(n + 1);
            else
                x2 = T.pre(c);
            ans -= dis(id[x1], x) + dis(x, id[x2]) - dis(id[x1], id[x2]);
        } else
            ans = 0;
    }
}
};  // namespace trivial_tree
using trivial_tree::add, trivial_tree::del;
vector<pair<int, int> > vec[N];
inline void ins(int u) {
    for (auto [v, w] : vec[u]) w < 0 ? del(v, -w) : add(v, w);
}
inline void del(int u) {
    for (auto [v, w] : vec[u]) w < 0 ? add(v, -w) : del(v, w);
}
inline void insx(int u) {
    ins(u);
    for (int i = h[u], v; i; i = edge[i].next)
        if ((v = edge[i].v) != fa[u]) insx(v);
}
inline void delx(int u) {
    del(u);
    for (int i = h[u], v; i; i = edge[i].next)
        if ((v = edge[i].v) != fa[u]) delx(v);
}
long long res = 0;
void dsu(int u) {
    for (int i = h[u], v; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == fa[u] || v == son[u]) continue;
        dsu(v), delx(v);
    }
    if (son[u]) dsu(son[u]);
    for (int i = h[u], v; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == fa[u] || v == son[u]) continue;
        insx(v);
    }
    ins(u);
    res += ans >> 1;
}
int main() {
    read(n, m);
    int u, v;
    for (int i = 1; i < n; i++) read(u, v), addedge(u, v), addedge(v, u);
    top[1] = 1, dfs(1), dfs2(1);
    for (int i = 1; i <= n; i++) vec[i].emplace_back(i, 1), vec[fa[i]].emplace_back(i, -1);
    for (int i = 1, u, v; i <= m; i++) {
        read(u, v), vec[u].emplace_back(v, 1), vec[u].emplace_back(u, 1);
        vec[v].emplace_back(v, 1), vec[v].emplace_back(u, 1);
        int g = lca(u, v);
        vec[g].emplace_back(u, -1), vec[g].emplace_back(v, -1);
        vec[fa[g]].emplace_back(u, -1), vec[fa[g]].emplace_back(v, -1);
    }
    dsu(1);
    cout << (res >> 1);
    return 0;
}

Luogu P7603 [THUPC2021] 鬼街

折半报警器，很巧妙。

$x$ 个数加起来 $\ge p$ 则至少有一个数 $\ge \dfrac p x$ ，用这个触发警报，警报后这几个位置的和至多只有原来的 $\dfrac x {x - 1}$ ，然后直接开堆维护即可，时间复杂度 $O(kq\log_{\frac k {k - 1}} V \log q)$ ， $k = 6$ 。

code

int n, m;
const int N = 1e5 + 10;
vector<pair<int, ll>> th[N];
int prime[N], cnt;
ll a[N], lim[N];
bool vis[N];
inline void init(int n) {
    vis[1] = 1;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
    t[N], tmp;
inline vector<int> frac(int x) {
    vector<int> ans;
    for (int i = 1; prime[i] * prime[i] <= x; i++)
        if (!(x % prime[i])) {
            ans.push_back(prime[i]);
            while (!(x % prime[i])) x /= prime[i];
        }
    if (x > 1) ans.emplace_back(x);
    return ans;
}
vector<int> rep;
bool used[N];
int tms[N], qcc;
inline void ring(int x, int uu) {
    if (used[x]) return t[uu].pop();
    ++qcc;
    ll qq = (lim[x] + th[x].size() - 1) / th[x].size();
    for (auto [u, v] : th[x])
        if (u == uu && a[u] < v + qq) return t[uu].pop();
    ll sumu = 0;
    for (auto &[u, v] : th[x]) sumu += a[u] - v, v = a[u];
    if (sumu >= lim[x]) return t[uu].pop(), used[x] = 1, rep.push_back(x);
    t[uu].pop();
    lim[x] -= sumu;
    qq = (lim[x] + th[x].size() - 1) / th[x].size();
    for (auto [u, v] : th[x]) t[u].push({v + qq, x});
}
inline void upd(int x, ll v) {
    a[x] += v;
    while (t[x].size() && a[x] >= t[x].top().first) {
        auto p = t[x].top();
        ring(p.second, x);
    }
}
int main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    init(100000);
    read(n, m);
    int last = 0, cc = 0;
    vector<int> tmp;
    for (int i = 1; i <= m; i++) {
        int op, x;
        ll y;
        read(op, x, y), y ^= last, tmp = frac(x);
        assert(tmp.size() <= 6);
        if (op == 0) {
            for (int v : tmp) upd(v, y);
            sort(rep.begin(), rep.end());
            write(last = rep.size(), ' ');
            for (int v : rep) write(v, ' ');
            println(), rep.clear();
        } else {
            ++cc;
            if (!y) {
                rep.push_back(cc);
                continue;
            }
            lim[cc] = y;
            ll qq = (lim[cc] + tmp.size() - 1) / tmp.size();
            for (int v : tmp)
                th[cc].emplace_back(v, a[v]), t[v].push({a[v] + qq, cc});
        }
        // cout << "after"s << i << endl;
    }
    cerr << double(clock()) / CLOCKS_PER_SEC << endl;
    return 0;
}

CF1336F Journey

大概只是比较长而已。

AT_dp_w Intervals

线段树优化 $\text{dp}$ 。

Luogu P6617 查找 Search

简单套路，略。

CF702F T-Shirts

将询问离线后对每个 $\text{T-shirts}$ 算，贡献用 $\text{FHQ-treap}$ 维护，顺序错乱的次数容易证明上界是 $O(n \log V)$ 的，直接维护即可。

Luogu P8421 [THUPC2022 决赛] rsraogps

很巧妙的。

对 $r$ 扫描线，另 $s_x$ 表示最短点为 $l$ 的答案，你发现大多数情况下 $s_x = r\times p_x + t_x$ ，有效的更新只有 $O(n \log V)$ 个，直接维护即可。

code

int n, m;
const int N = 1e6 + 10, Q = 5e6 + 10;
int lle[Q], rr[Q];
pair<int, int> *vec[N], qt[Q], *ppq;
int cnt[N];
int ans[Q], a[N], b[N], c[N], lst[N], p[N], r[N], T;
inline int query(int x) { return p[x] + r[x] * (T - lst[x]); }
signed main() {
    read(n), read(m);
    ppq = qt;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) read(b[i]);
    for (int i = 1; i <= n; i++) read(c[i]);
    for (int i = 1, l, r; i <= m; i++) read(lle[i]), read(rr[i]), ++cnt[rr[i]];
    for (int i = 1; i <= n; i++) vec[i] = ppq, ppq += cnt[i], cnt[i] = 0;
    for (int i = 1; i <= m; i++) vec[rr[i]][cnt[rr[i]]++] = {i, lle[i]};
    int aa, bb, cc, px, py, pz, x, qq;
    for (int i = 1; i <= n; i++) {
        px = py = pz = i - 1;
        while (px) {
            aa = a[px] & a[px + 1];
            if (a[px] == aa) break;
            a[px] = aa, --px;
        }
        while (py) {
            aa = b[py] | b[py + 1];
            if (b[py] == aa) break;
            b[py] = aa, --py;
        }
        while (pz) {
            aa = gcd(c[pz], c[pz + 1]);
            if (c[pz] == aa) break;
            c[pz] = aa, --pz;
        }
        x = min({px, py, pz});
        p[i] = query(i - 1);
        for (int j = x + 1; j <= i; j++)
            p[j] = query(j), r[j] = r[j - 1] + a[j] * b[j] * c[j], lst[j] = T;
        ++T, qq = query(i);
        for (int j = 0; j < cnt[i]; j++) ans[vec[i][j].first] = qq - query(vec[i][j].second - 1);
    }
    for (int i = 1; i <= m; i++) write(ans[i]), pc('\n');
    return 0;
}

CF878D Magic Breeding

这题好难好难好难好难好难好难好难好难好难好难好难好难好难。

你先把数离散化掉，显然是可以的。

然后考虑一些神奇的东西，这玩意儿可以简单的转化为 $01$ ，比如

$1,2,3$ 可以变为 $100, 110, 111$ 。

然后本质不同的列只有 $4096$ 种，配合 $\text{bitset}$ 维护即可。

code

const int N = 1e5 + 10, K = 13;
int n, k, q;
bitset<1 << 12> f[N + 14];
int a[N][14], tab[N][14];
unsigned g[N * 13];
int main() {
    read(n), read(k), read(q);
    int cnt = k;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= n; j++) read(a[j][i]);
    for (int i = 1; i <= n; i++) {
        memcpy(tab[i], a[i], sizeof(tab[i]));
        sort(tab[i] + 1, tab[i] + k + 1);
        for (int j = 1; j <= k; j++) {
            int t = lower_bound(tab[i] + 1, tab[i] + k + 1, a[i][j]) - tab[i];
            for (int l = 1; l <= t; l++) g[(i - 1) * 12 + l] |= 1u << j - 1;
        }
    }
    for (int i = 1; i <= k; i++)
        for (int j = 0; j < 4096; j++)
            if (j & (1 << i - 1)) f[i].set(j);
    int op, x, y;
    for (int i = 1; i <= q; i++) {
        read(op), read(x), read(y);
        if (op == 1)
            ++cnt, f[cnt] = f[x] | f[y];
        else if (op == 2)
            ++cnt, f[cnt] = f[x] & f[y];
        else if (op == 3) {
            int t = 0;
            for (int l = 1; l <= k; l++)
                if (f[x].test(g[(y - 1) * 12 + l])) ++t;
            write(tab[y][t]), putc('\n');
        }
    }
    do_flush();
    return 0;
}

CF605D Board Game

$\text{BIT}$ 优化 $\text{BFS}$ 。

CF372D Choosing Subtree is Fun

双指针 $+$ $\text{set}$ + $\text{dfn}$ 序求斯坦纳树大小即可。

Luogu P5685 [JSOI2013] 快乐的 JYY

$\text{PAM}$ 求交板子题。

Luogu P5068 [Ynoi2015] 我回来了

大常数做法比较好想，小常数离线做法比较有趣，，。

考虑用 $g_{i,j}$ 表示第一次伤害值为 $i$ 能打 $k$ 次的时间。

由于 $i(j - 1) + 1 \le n$ ，所以有效的 $(i,j)$ 个数为 $O(n \log n)$ 。

记录 $p_i$ 为生命值为 $i$ 的仆从第一次出现的时间，然后 $g$ 的计算可以直接 $\text{ST}$ 表做。

把 $(g_{i,j},i)$ 当作一个点，然后二维数点即可。

时间复杂度 $O(n \log^2n + m\log n)$ 。

代码中我使用了期望 $O(n)-O(1) \text{ rmq}$ 和手写 $\text{vector}$ 。

code

const int N = 1e5 + 10, M = 1e6 + 10;
template <const int S, const int L, typename T>
struct darry {
    pair<int, T> a[S];
    T chi[S];
    T *top[L], *nt;
    int sz[L], len;
    struct vector_helper {
        darry &arr;
        int posx;
        inline T *begin() { return arr.top[posx]; }
        inline T *end() { return arr.top[posx] + arr.sz[posx]; }
        inline void push(T x) { arr.a[++arr.len] = {posx, x}; }
    };
    inline void build() {
        nt = chi, memset(sz, 0, sizeof(sz));
#pragma GCC unroll 8
        for (int i = 1; i <= len; i++) ++sz[a[i].first];
#pragma GCC unroll 8
        for (int i = 0; i < L; i++) top[i] = nt, nt += sz[i], sz[i] = 0;
#pragma GCC unroll 8
        for (int i = 1; i <= len; i++)
            top[a[i].first][sz[a[i].first]++] = a[i].second;
    }
    inline vector_helper operator[](int x) { return {*this, x}; }
};
// vector<pair<int, int> >
darry<M << 1, N, int> Q;
template <typename T, int L>
struct ST {
    constexpr static int s = 32;
    int pos[L];
    inline void initlg(int n) {
        for (int i = 1; i <= n; i++) pos[i] = (i - 1) / s + 1;
        pos[n + 1] = 0;
    }
    T st[19][(L + 64) / s], *p;
    T pre[L], nxt[L];
    inline void setup(int n, T *x) {
        p = x;
        memset(pre, 0x3f, sizeof(pre)), memset(st, 0x3f, sizeof(st)), memset(nxt, 0x3f, sizeof(nxt));
        for (int i = 1; i <= n; i++) st[0][pos[i]] = min(st[0][pos[i]], x[i]);
        for (int i = 1; i < 19; i++)
            for (int j = 1; j + (1 << i) - 1 <= pos[n]; j++)
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
        for (int i = 1; i <= n; i++)
            if (pos[i] != pos[i - 1])
                pre[i] = x[i];
            else
                pre[i] = min(x[i], pre[i - 1]);
        for (int i = n; i; i--)
            if (pos[i] != pos[i + 1])
                nxt[i] = x[i];
            else
                nxt[i] = min(x[i], nxt[i + 1]);
    }
    inline T query(int l, int r) {
        if (pos[l] == pos[r]) {
            T ans = 0x3f3f3f3f;
            for (int i = l; i <= r; i++) chkmin(ans, p[i]);
            return ans;
        }
        if (pos[l] + 1 == pos[r]) return min(nxt[l], pre[r]);
        int t = __lg(pos[r] - pos[l] - 1);
        return min({nxt[l], pre[r], st[t][pos[l] + 1],
                    st[t][pos[r] - 1 - (1 << t) + 1]});
    }
};
ST<int, N> s;
pair<int, int> g[N * 25];
int top;
int a[N], n, m;
int ans[M];
struct BIT {
#define low(x) ((x) & -(x))
    int w[M];
    inline void update(int u, int v) {
        while (u <= m) w[u] += v, u += low(u);
    }
    inline int query(int u) {
        int ans = 0;
        while (u) ans += w[u], u ^= low(u);
        return ans;
    }
} T;
bool vis[M];
int main() {
    read(n, m);
    memset(a, 0x3f, sizeof(a));
    for (int i = 1; i <= m; i++) {
        // read(p[i].op);
        int op, a, b;
        read(op);
        if (op == 1) {
            read(a);
            chkmin(::a[a], i);
        } else {
            read(a, b);
            Q[b].push(i), Q[a - 1].push(-i), vis[i] = 1;
            ans[i] = b - a + 1;
        }
    }
    Q.build(), s.initlg(n), s.setup(n, a);
    for (int i = 1; i <= n; i++) {
        int x = 0;
        for (int j = 1; (j - 1) * i + 1 <= n; j++) chkmax(x, s.query((j - 1) * i + 1, min(n, j * i))), g[++top] = {i, x};
    }
    int r = 1;
    for (int i = 1; i <= n; i++) {
        while (r <= top && g[r].first <= i) T.update(g[r++].second, 1);
        for (int v : Q[i]) ans[abs(v)] += v < 0 ? -T.query(-v) : T.query(v);
    }
    for (int i = 1; i <= m; i++) if (vis[i]) println(ans[i]);
    return 0;
}

Luogu P4192 旅行规划

指令集练习题，正解含金量太低了。

CF1866F Freak Joker Process

指令集练习题。

AT_cf17_final_j Tree MST

$\text{Kruskal}$ 算法是很巧妙的。

一般地，对于完全图 $\text{MST}$ 问题，我们可以先选定一个边集，做一次 $\text{MST}$ (不连通不管)，把剩余的边保留，最后再做一次 $\text{MST}$ ，这样一定能得到最优解。（引用自（本文）[https://www.luogu.com.cn/blog/command-block/solution-at3611]）

然后点分治后，我们发现，跨过点 $u$ 时，我们发现每个点点权设为 $dis(u, i) + w_i$ ，然后所有的点都应该向点权最小的连边。

代码运用来排序求最小值，请勿学习 >_<，时间复杂度 $O(n \log^2)$ 。

code

#define int long long
hash_map<int, bool> mp;
const int N = 2e5 + 10;
struct Edge {
    int next, v, w;
} edge[N << 1];
int h[N], cnt;
inline void addedge(int u, int v, int w) { edge[++cnt] = {h[u], v, w}, h[u] = cnt; }
ll dis[N];
int n, m, scc[N], siz[N], msz[N], cent, dcnt = 0, a[N];
bool vis[N];
void findcent(int u, int f, int sum) {
    siz[u] = 1, msz[u] = 0;
    int v;
    for (int i = h[u]; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == f || vis[v]) continue;
        findcent(v, u, sum), siz[u] += siz[v];
        if (siz[v] > msz[u]) msz[u] = siz[v];
    }
    msz[u] = max(msz[u], sum - siz[u]);
    if (msz[u] < msz[cent]) cent = u;
}
vector<pair<ll, int> > vec;
void makedis(int u, int f, int fr) {
    int v;
    scc[u] = fr;
    vec.emplace_back(dis[u] + a[u], u);
    for (int i = h[u]; i; i = edge[i].next) {
        v = edge[i].v;
        if (v == f || vis[v]) continue;
        dis[v] = dis[u] + edge[i].w, makedis(v, u, fr);
    }
}
ll ans = 0;
struct Line {
    int u, v;
    ll w;
    inline bool operator<(Line b) const { return w < b.w; }
};
int fa[N];
vector<Line> c;
inline void solve(int u) {
    clear(vec), mp.clear();
    for (int i = h[u], v; i; i = edge[i].next) if (!vis[v = edge[i].v]) dis[v] = edge[i].w, makedis(v, u, v);
    vec.emplace_back(a[u], u), sort(vec.begin(), vec.end());
    mp[vec[0].second] = 1;
    ll k = vec[0].first;
    for (auto [u, v] : vec) c.push_back({vec[0].second, v, k + u});
}
void divcent(int u, int sum) {
    cent = 0, findcent(u, u, sum), vis[cent] = 1, solve(cent);
    int tmp = cent, v;
    for (int i = h[tmp]; i; i = edge[i].next) {
        v = edge[i].v;
        if (!vis[v]) divcent(v, siz[v] < siz[tmp] ? siz[v] : sum - siz[tmp]);
    }
}
inline int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }
signed main() {
    read(n), msz[0] = 0x3f3f3f3f;
    int u, v, w;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i < n; i++) read(u, v, w), addedge(u, v, w), addedge(v, u, w);
    divcent(1, n);
    sort(c.begin(), c.end());
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (auto [u, v, w] : c)
        if (find(u) != find(v)) fa[find(u)] = find(v), ans += w;
    println(ans);
    return 0;
}

CF715C Digit Tree

点分治板子题，不推荐。

Luogu P8991 北大集训 2021 出题高手

乱搞题啦！

发现随着区间长度的增长， $\sum$ 的增长不是很明显，但长度的变化会很明显，猜测答案在区间长度 $\le x$ ，其中 $x$ 为常数，代码中取了约为 $2000$ 的数，并且特判了 $m = 1$ ， $n$ 很大的 $\text{subtask}$ 。

code

const int N = 5e5 + 10;
struct Frac {
    ll x, y;
    inline bool operator<(Frac b) const { return x * b.y < y * b.x; }
    inline void pc() {
        ll c = __gcd(x, y);
        println(x / c, y / c);
    }
};
int n, m, a[N];
ll s[N];
Frac ans[N];
struct BIT {
#define low(x) ((x) & -(x))
    Frac w[N];
    inline void update(int u, Frac v) {
        while (u) chkmax(w[u], v), u ^= low(u);
    }
    inline Frac query(int u) {
        Frac ans = {0, 1};
        while (u <= n) chkmax(ans, w[u]), u += low(u);
        return ans;
    }
    inline BIT() {
        for (int i = 0; i < N; i++) w[i] = {0, 1};
    }
} f;
vector<pair<int, int> > vec[N];
int sz;
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), s[i] = s[i - 1] + a[i];
    read(m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        read(l, r), vec[r].emplace_back(l, i);
    }
    if (m == 1) sz = 500;
    else sz = 2000;
    for (int i = 1; i <= n; i++) {
        Frac now = {0, 1};
        for (int j = i; j >= 1 && i - j <= sz; j--) {
            Frac res = {(s[i] - s[j - 1]) * (s[i] - s[j - 1]), i - j + 1};
            if (now < res)
                f.update(j, res), now = res;
        }
        for (auto [l, id] : vec[i]) ans[id] = f.query(l);
    }
    for (int i = 1; i <= m; i++) ans[i].pc();
    return 0;
}

Luogu P3765 总统选举

摩尔投票法板子题。

CF700D Huffman Coding on Segment

直接做的做法是哈夫曼树，经典结论是发现区间颜色数量的种类数是 $O(\sqrt n)$ 的，因此直接做就行了。

代码中采用了莫队和根号分治。

时间复杂度 $O(n \sqrt n \log ^c n)$ ， $c$ 取决于实现。

code

const int N = 1e5 + 10;
int c[N], n, m, a[N], pos[N], s, B;
struct Query {
    int l, r, id;
    inline bool operator<(Query b) {
        return pos[l] == pos[b.l] ? (pos[l] & 1 ? r < b.r : r > b.r) : l < b.l;
    }
} q[N];
int cnt[N], t2[N], t[N];
multiset<int> s1, s2;
inline void add(int x) {
    --t[cnt[x]];
    if ((++cnt[x]) == B) s1.insert(x);
    ++t[cnt[x]];
}
inline void del(int x) {
    --t[cnt[x]];
    if ((cnt[x]--) == B) s1.erase(s1.find(x));
    ++t[cnt[x]];
}
ll ans = 0;
inline void adds(int x, int k) {
    ans += 1ll * x * k;
    if (x < B)
        t2[x] += k;
    else
        while (k--) s2.insert(x);
}
inline ll query() {
    ans = 0;
    clear(s2);
    for (int v : s1) s2.insert(cnt[v]);
    memcpy(t2, t, sizeof(t2[0]) * (B + 1));
    int pre = 0;
    for (int i = 1; i < B; i++)
        if (t2[i]) {
            if (pre) --t2[i], adds(i + pre, 1), pre = 0;
            int c = t2[i] >> 1;
            if (c) adds(i << 1, c);
            t2[i] = t2[i] & 1;
            if (t2[i]) pre = i;
        }
    if (pre) s2.insert(pre);
    while (s2.size() >= 2) {
        int x = *s2.begin();
        s2.erase(s2.begin());
        int y = *s2.begin();
        s2.erase(s2.begin()), ans += x + y, s2.insert(x + y);
    }
    return ans;
}
ll p[N];
int main() {
    read(n), B = sqrt(n * log2(n));
    for (int i = 1; i <= n; i++) read(a[i]);
    // cout << "s:" << s << endl;
    read(m), s = n / max(1.0, sqrt(m)) + 1;
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / s + 1; 
    for (int i = 1; i <= m; i++) read(q[i].l, q[i].r), q[i].id = i;
    sort(q + 1, q + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        p[q[i].id] = query();
    }
    for (int i = 1; i <= m; i++) println(p[i]);
    return 0;
}

CF1553H XOR and Distance

异或一位相当于交换 $\text{trie}$ 上的左右孩子，对于 $\text{01trie}$ 上的每个节点预处理出 $[0, 2^x)$ （ $2^x$ 即子树表示的范围大小），然后发现复杂度是 $\text{01trie}$ 上 $\sum siz$ ，即 $O(k2^k)$ 。

code

const int N = 6e5 + 10;
vector<int> f[N << 1], mn[N << 1], mx[N << 1];
int n, ch[N << 1][2], cnt, dep[N << 1], k;
void insert(int x) {
    int u = 0;
    for (int i = 19; ~i; i--) {
        bool h = (x >> i) & 1;
        dep[u] = i;
        if (!ch[u][h]) ch[u][h] = ++cnt;
        u = ch[u][h];
    }
}
vector<int> I;
void solve(int u) {
    if (!ch[u][0] && !ch[u][1]) return mn[u] = mx[u] = {0}, f[u] = {inf}, void();
    if (ch[u][0]) solve(ch[u][0]);
    if (ch[u][1]) solve(ch[u][1]);
    f[u].resize(1 << dep[u] + 1);
    mn[u].resize(1 << dep[u] + 1);
    mx[u].resize(1 << dep[u] + 1);
    for (int i = 0; i < (1 << dep[u] + 1); i++) f[u][i] = inf;
    for (int i = 0; i < (1 << dep[u]); i++) {
        f[u][i] = min({f[ch[u][0]][i], f[ch[u][1]][i], mn[ch[u][1]][i] + (1 << dep[u]) - mx[ch[u][0]][i]});
        f[u][i | (1 << dep[u])] = min({f[ch[u][0]][i], f[ch[u][1]][i], mn[ch[u][0]][i] + (1 << dep[u]) - mx[ch[u][1]][i]});
        mn[u][i] = min(mn[ch[u][0]][i], mn[ch[u][1]][i] + (1 << dep[u]));
        mn[u][i | (1 << dep[u])] = min(mn[ch[u][0]][i]  + (1 << dep[u]), mn[ch[u][1]][i]);
        mx[u][i] = max(mx[ch[u][0]][i], mx[ch[u][1]][i] + (1 << dep[u]));
        mx[u][i | (1 << dep[u])] = max(mx[ch[u][0]][i]  + (1 << dep[u]), mx[ch[u][1]][i]);
    }
}
int main() {
    I.resize(1), I[0] = 0;
    mn[0].resize(N << 1);
    mx[0].resize(N << 1);
    f[0].resize(N << 1);
    for (int i = 0; i < (N << 1); i++) f[0][i] = inf, mn[0][i] = inf, mx[0][i] = -inf;
    read(n, k);
    for (int i = 1, x; i <= n; i++) read(x), insert(x);
    solve(0);
    for (int i = 0; i < (1 << k); i++) write(f[0][i], ' ');
    return 0;
}

CF1140G Double Tree

大宝树。

$\text{ddp}$ 板子题。

code

const int N = 3e5 + 10;
int n, a[N], m;
ll f[N];
struct Matrix{
    ll mat[2][2];
    inline Matrix operator*(Matrix b) {
        Matrix ans;
        ans.mat[0][0] = min(mat[0][0] + b.mat[0][0], mat[0][1] + b.mat[1][0]);
        ans.mat[0][1] = min(mat[0][0] + b.mat[0][1], mat[0][1] + b.mat[1][1]);
        ans.mat[1][0] = min(mat[1][0] + b.mat[0][0], mat[1][1] + b.mat[1][0]);
        ans.mat[1][1] = min(mat[1][0] + b.mat[0][1], mat[1][1] + b.mat[1][1]);
        return ans;
    }
} g[N], val[20][N], rev[20][N];
vector<tuple<int, ll, ll> > vec[N];
int dep[N], fa[20][N];
inline int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v]) u = fa[__lg(dep[u] - dep[v])][u];
    if (u == v) return u;
    for (int i = __lg(dep[u]); ~i; i--)
        if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v];
    return fa[0][u];
}
void dp(int u) {
    for (auto [v, w1, w2] : vec[u]) if (v != fa[0][u]) fa[0][v] = u, dp(v), chkmin(f[u], f[v] + w1 + w2);
}
void dp2(int u) {
    g[u] = {0, f[u], f[u], 0};
    for (auto [v, w1, w2] : vec[u]) if (v != fa[0][u]) dep[v] = dep[u] + 1, chkmin(f[v], f[u] + w1 + w2), dp2(v);
}
void dfs(int u) {
    for (auto [v, w1, w2] : vec[u]) if (v != fa[0][u])
        val[0][v] = g[v] * Matrix{w1, INF, INF, w2}, rev[0][v] = Matrix{w1, INF, INF, w2} * g[v], dfs(v);
}
inline ll query(int u, int v) {
    int a = u & 1, b = v & 1;
    u += a, v += b, u >>= 1, v >>= 1;
    int l = lca(u, v);
    Matrix ans = {0, INF, INF, 0}, ans2 = {0, INF, INF, 0};
    while (u != l) {
        int c = __lg(dep[u] - dep[l]);
        ans = ans * val[c][u], u = fa[c][u];
    }
    while (v != l) {
        int c = __lg(dep[v] - dep[l]);
        ans2 = rev[c][v] * ans2, v = fa[c][v];
    }
    ans = ans * g[l] * ans2;
    return ans.mat[a ^ 1][b ^ 1];
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(f[i]);
    int u, v;
    ll w1, w2;
    for (int i = 1; i < n ;i++)
        read(u, v, w1, w2), vec[u].emplace_back(v, w1, w2), vec[v].emplace_back(u, w1, w2);
    dp((dep[1] = 1, 1)), dp2(1), dfs(1);
    for (int i = 1; i <= __lg(n); i++)
        for (int j = 1; j <= n; j++) if (dep[j] >= (1 << i)) {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
            val[i][j] = val[i - 1][j] * val[i - 1][fa[i - 1][j]];
            rev[i][j] = rev[i - 1][fa[i - 1][j]] * rev[i - 1][j];
        }
    read(m);
    while (m--) read(u, v), println(query(u, v));
    return 0;
}

CF1149C Tree Generator™

令 $h_i$ 为括号 $i$ 处的深度，那么答案可以转化为 $\max_{x\le y \le z} h_x + h_z - 2h_y$ 。

然后直接做就行了。

code

const int N = 1e6 + 10;
struct Node {
    int mn, mx, lp, rp, ™;
} w[N << 2];
int tag[N << 2];
inline Node operator+(Node a, Node b) {
    return {min(a.mn, b.mn), max(a.mx, b.mx), max({a.lp, b.lp, a.mx - 2 * b.mn}), max({a.rp, b.rp, b.mx - 2 * a.mn}), max({a.™, b.™, a.mx + b.rp, a.lp + b.mx})};
}
inline void maketag(int u, int v) {
    w[u].mn += v, w[u].mx += v, w[u].lp -= v, w[u].rp -= v, tag[u] += v;
}
inline void pushdown(int u) {
    if (tag[u]) maketag(u << 1, tag[u]), maketag(u << 1 | 1, tag[u]), tag[u] = 0;
}
template<int v>
void update(int u, int L, int R, int l, int r) {
    if (L >= l && R <= r) return maketag(u, v);
    int M = L + R >> 1;
    pushdown(u);
    if (l <= M) update<v>(u << 1, L, M, l, r);
    if (M < r) update<v>(u << 1 | 1 , M + 1, R, l, r);
    w[u] = w[u << 1] + w[u << 1 | 1];
}
char str[N];
int a[N], n, m;
void build(int u, int L, int R) {
    if (L == R) return void(w[u] = {a[L], a[L], -a[L], -a[L], 0});
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R), w[u] = w[u << 1] + w[u << 1 | 1];
}
int main() {
    read(n, m), read_cstr(str + 1), n = 2 * n - 2;
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + ((str[i] == '(') ? 1 : -1);
    build(1, 1, n), println(max(w[1].mx, w[1].™));
    while (m--) {
        int x, y;
        read(x, y);
        if (x > y) swap(x, y);
		if (str[x] == '(' && str[y] == ')') update<-2>(1, 1, n, x, y - 1);
		else if (str[x] == ')' && str[y] == '(') update<2>(1, 1, n, x, y - 1);
        swap(str[x], str[y]), println(max(w[1].mx, w[1].™));
    }
    return 0;
}

CF487E Tourists

先建立出圆方树，圆点权值是自己，方点权值是周围圆点 $\max$ 。

然后发现更改一个圆点要更改周围所有方点？？？？

不是的，我们只更新圆方树上的父亲吗，然后查询的时候，如果 $\text{lca}$ 是方点，那么看一下 $\text{lca}$ 的父亲，也就是那个圆点的值算入答案。

复杂度 $O(n \text{polylog})$ 。

code

const int N = 5e5 + 10, M = 5e5 + 10;
vector<int> vec[N];
int n, m, dfn[N], top, low[N], cur, s[N], bcnt;
vector<int> bcc[M];
void tarjan(int u, int fa) {
    int son = 0;
    low[u] = dfn[u] = ++cur, s[++top] = u;
    for (int v : vec[u])
        if (!dfn[v]) {
            ++son, tarjan(v, u), chkmin(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++bcnt;
                while (s[top + 1] != v) bcc[bcnt].push_back(s[top--]);
                bcc[bcnt].push_back(u);
            }
        } else if (v != fa)
            chkmin(low[u], dfn[v]);
    if (!fa && !son) bcc[++bcnt].push_back(u);
}
vector<int> qt[N + M];
int siz[N + M], son[N + M], val[N + M], lit[N + M], fa[N + M], dep[N + M];
int v[N], ch[N][2], g[N], sum[N];
void dfs(int u) {
    val[u] += u <= n, siz[u] = 1;
    for (int v : qt[u]) if (v != fa[u]) {
        dep[v] = dep[u] + 1, val[v] = val[u], g[v] = fa[v] = u, dfs(v), siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u) {
    for (int v : qt[u]) {
        if (v == fa[u]) continue;
        lit[v] = (v == son[u]) ? lit[u] : v, dfs2(v);
    }
}
inline int lca(int u, int v) {
    while (lit[u] != lit[v])
        dep[lit[u]] > dep[lit[v]] ? u = fa[lit[u]] : v = fa[lit[v]];
    return dep[u] < dep[v] ? u : v;
}
inline int query(int u, int v) {
    int c = lca(u, v);
    return val[u] + val[v] - val[c] - val[fa[c]];
}
multiset<int> T[N + M];
bool lzy[N];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
inline bool isroot(int u) { return ch[g[u]][0] != u && ch[g[u]][1] != u; }
inline void connect(int u, int v, bool k) { ch[u][k] = v, g[v] = u; }
inline bool get(int u) { return rc(g[u]) == u; }
inline void pushup(int u) {
    if (u) sum[u] = min({sum[lc(u)], v[u], sum[rc(u)]});
}
inline void maketag(int u) { lzy[u] ^= 1, swap(lc(u), rc(u)); }
inline void pushdown(int u) {
    if (lzy[u]) {
        if (lc(u)) maketag(lc(u));
        if (rc(u)) maketag(rc(u));
        lzy[u] = 0;
    }
}
inline void update(int u) {
    if (!isroot(u)) update(g[u]);
    pushdown(u);
}
inline void rotate(int u) {
    bool k = get(u), kf = get(g[u]);
    int f = g[u];
    if (isroot(f))
        g[u] = g[f];
    else
        connect(g[f], u, kf);
    connect(f, ch[u][k ^ 1], k), connect(u, f, k ^ 1);
    pushup(f), pushup(u);
}
inline void splay(int u) {
    update(u);
    for (int f = g[u]; f = g[u], !isroot(u); rotate(u))
        if (!isroot(f)) rotate(get(u) == get(f) ? f : u);
}
inline void access(int u) {
    for (int f = 0; u; u = g[f = u]) splay(u), rc(u) = f, pushup(u);
}
inline void makeroot(int u) { access(u), splay(u), maketag(u); }
inline void split(int u, int v) { makeroot(u), access(v), splay(v); }
inline int xval(int u) {
    return T[u].size() ? *T[u].begin() : inf;
}
inline void reset(int u, int w) { splay(u), v[u] = w, pushup(u); }
int main() {
    sum[0] = 0x3f3f3f3f;
    int q, a, b;
    char op;
    read(n, m, q);
    int u, v;
    for (int i = 1; i <= n; i++) read(::v[i]);
    for (int i = 1; i <= m; i++)
        read(u, v), vec[u].push_back(v), vec[v].push_back(u);
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) top = 0, tarjan(i, 0);
    for (int i = 1; i <= bcnt; i++)
        for (int v : bcc[i])  qt[v].push_back(i + n), qt[i + n].push_back(v);
    dep[1] = lit[1] = 1, dfs(1), dfs2(1);
    for (int i = 1; i <= n; i++) {
        sum[i] = ::v[i];
        if (fa[i] > n) T[fa[i]].insert(::v[i]);
    }
    for (int i = n + 1; i <= n + bcnt; i++) ::v[i] = sum[i] = xval(i);
    while (q--) {
        read(op, a, b);
        if (op == 'C') {
            if (fa[a] > n) {
                T[fa[a]].erase(T[fa[a]].find(::v[a]));
                reset(a, b);
                T[fa[a]].insert(::v[a]);
                reset(fa[a], xval(fa[a]));
            } else reset(a, b);
        } else {
            split(a, b);
            int ans = sum[b], k = lca(a, b);
            if (fa[k] >= 1 && fa[k] <= n && k > n) chkmin(ans, ::v[fa[k]]);
            println(ans);
        }
    }
    return 0;
}

CF875E Delivery Club

二分答案，然后模拟即可。

复杂度 $O(n \log ^2)$ 。

code

const int N = 1e6 + 10;
int a[N], n, pa, pb;
inline bool check(int x) {
    set<int> c{pa, pb};
    for (int i = 1; i <= n; i++) {
        c.erase(c.begin(), c.lower_bound(a[i] - x)), c.erase(c.upper_bound(a[i] + x), c.end());
        if (!c.size()) return 0;
        c.insert(a[i]);
    }
    return 1;
}
signed main() {
    read(n, pa, pb);
    for (int i = 1; i <= n; i++) read(a[i]);
    int L = abs(pb - pa), R = 0x3f3f3f3f, ans, mid;
    while (mid = L + R >> 1, L <= R) check(mid) ? R = mid - 1, ans = mid : L = mid + 1;
    println(ans);
    return 0;
}

CF1017H The Films

简单推波柿子，然后对于每个 $k$ 分别莫队即可，复杂度 $O(n \sqrt{qt})$ ，其中 $t$ 表示不同 $k$ 的个数，为 $100$ 。

code

const int N = 1e5 + 10;
int pos[N];
struct Query {
    int l, r, id;
    inline bool operator<(Query b) { return pos[l] == pos[b.l] ? (pos[l] & 1 ? r < b.r : r > b.r) : l < b.l; }
};
ll zi, mu, ans;
const ll P = 998244353;
int n, m, res[N], q, f[N], s, a[N], cc[N], b[N];
vector<Query> v[N];
inline void add(int x) {
    zi = zi * (cc[x] - (b[x]++)) % P;
}
inline void del(int x) {
    mu = mu * (cc[x] - (--b[x])) % P;
}
inline ll qpw(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % P;
        a = a * a % P, b >>= 1;
    }
    return ans;
}
inline void solve(int x) {
    if (!v[x].size()) return;
    s = max(1, int(n / (1 + sqrt(2 * v[x].size() / 3))));
    for (int i = 1; i <= n; i++) pos[i] = (i - 1) / s + 1;
    sort(v[x].begin(), v[x].end());
    int l = 1, r =0 ;
    zi = mu = 1;
    memset(cc, 0, sizeof(cc));
    memset(b, 0, sizeof(b));
    f[0] = 1;
    ll c = 1ll * x * m % P;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] * (c + i) % P;
    for (int i = 1; i <= n; i++) ++cc[a[i]];
    for (int i = 1; i <= m; i++) cc[i] += x;
    for (auto [ql, qr, id] : v[x]) {
        while (r < qr) add(a[++r]);
        while (l > ql) add(a[--l]);
        while (r > qr) del(a[r--]);
        while (l < ql) del(a[l++]);
        res[id] = zi * qpw(mu, P - 2) % P * f[n - (qr - ql + 1)] % P;
    }
}
int main() {
    read(n, m, q);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= q; i++) {
        int l, r, k;
        read(l, r, k), v[k].push_back({l, r, i});
    }
    for (int i = 0; i <= 100000; i++) solve(i);
    for (int i = 1; i <= q; i++) println(res[i]);
    return 0;
}

Luogu P5381 [THUPC2019] 不等式

如果 $a_i$ 都是 $1$ ，那么把柿子转化为 $\min x \sum |x - t_i|$ 之后其意义就是数轴上距离和最近，答案显然是中位数。如果 $a_i$ 不是 $1$ 那么可以看成插入了 $a_i$ 个数，然后特判 $a_i = 0$ 即可。

code

const int N = 1e6 + 10;
struct Node {
    int l, r;
    ld v, sum;
    ll siz, cnt;
} w[N];
#define lc(u) w[u].l
#define rc(u) w[u].r
inline void pushup(int u) { w[u].sum = w[lc(u)].sum + w[rc(u)].sum + w[u].v * w[u].cnt; w[u].siz = w[lc(u)].siz + w[u].cnt + w[rc(u)].siz; }
int root, cnt, n;
void insert(int &u, Node v) {
    if (!u) {
        u = ++cnt, w[u] = v;
        return;
    }
    if (w[u].v < v.v) insert(rc(u), v);
    else insert(lc(u), v);
    pushup(u);
}
ld sum = 0;
inline void output(ld c) {
    write(ll(c)), pc('.');
    ll k = __int128(c * ld(1e6)) % 1000000;
    int len = 0;
    ll pk = k;
    while (pk) pk /= 10, ++len;
    len = 6 - len;
    while (len--) pc('0');
    write(k), pc('\n');
}
inline void solve() {
    if (!root) return output(sum);
    int u = root;
    long double lv = 0, rv = 0;
    int ls = 0, rs = 0;
    ll k = w[u].siz + 1 >> 1;
    while (1) {
        if (k <= w[lc(u)].siz) rs += w[u].cnt + w[rc(u)].siz, rv += w[u].v * w[u].cnt + w[rc(u)].sum, u = lc(u);
        else if (k <= w[lc(u)].siz + w[u].cnt) {
            rs += w[rc(u)].siz, rv += w[rc(u)].sum; 
            ls += w[lc(u)].siz, lv += w[lc(u)].sum; 
            break;
        } else
            k -= w[lc(u)].siz + w[u].cnt, ls += w[u].cnt + w[lc(u)].siz, lv += w[u].v * w[u].cnt + w[lc(u)].sum, u = rc(u);
    }
    output(sum + (ls - rs) * w[u].v + rv - lv);
}
ll a[N], b[N];
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) read(b[i]);
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) sum += abs(b[i]);
        else {
            ld c = -ld(b[i]) / a[i];
            insert(root, {0, 0, c, c * abs(a[i]), abs(a[i]), abs(a[i])});
        }
        solve();
    }
    return 0;
}

Luogu P5443 [APIO2019] 桥梁

垃圾分块题。

CF713D Animals and Puzzle

二分简单题。

Luogu P9607 [CERC2019] Be Geeks!

对最大值做笛卡尔树。

然后问题变为给定 $p,q,t$ , 求 $\sum_{p \le l \le q,q \le r \le t} \gcd_{l \le i \le r}(a_i)$

我们定义 $f(x, y) = \sum_{x \le l \le r \le y} \gcd_{l \le i \le r} (a_i)$ ，那么原问题可以差分为 $f(p, t) - f(p, q - 1) - f(q + 1, t)$ 。

$f$ 的求解可以用该题的做法解决，时间复杂度 $O(n \log V)$ 。

JOISC2016 回転寿司

有点意思。

我们发现如果全局操作：最大值如果大于 $A$ ，那么一定会弹出去；还有就是我们可以扫一遍算出每个位置在操作后的值，具体做法是我们发现答案与操作顺序无关，对修改做优先队列，然后每次都是队列中最小值和当前值的最小值，如果当前位置得到更新，那么要弹出最小值放入该位置原值。

时间复杂度 $O(n \sqrt n \log n)$ 。

code

const int N = 4e5 + 10;
int a[N], n, m, e[N], f[N];
int pos[N], s;
priority_queue<int, vector<int>, greater<int> > tag[N];
priority_queue<int> val[N];
inline void rebuild(int u) {
    if (tag[u].size())
        for (int i = f[u]; i <= e[u]; i++)
            if (a[i] > tag[u].top()) {
                int c = tag[u].top();
                tag[u].pop(), tag[u].push(a[i]), a[i] = c;
            }
    clear(tag[u]), clear(val[u]);
}
inline int updsan(int l, int r, int v) {
    rebuild(pos[l]);
    for (int i = l; i <= r; i++)
        if (v < a[i]) swap(a[i], v);
    for (int i = f[pos[l]]; i <= e[pos[l]]; i++) val[pos[l]].push(a[i]);
    return v;
}
inline int updzen(int u, int v) {
    if (v >= val[u].top()) return v;
    int res = val[u].top();
    val[u].pop(), val[u].push(v), tag[u].push(v);
    return res;
}
inline int upd(int l, int r, int v) {
    if (pos[l] == pos[r]) return updsan(l, r, v);
    int c = updsan(l, e[pos[l]], v);
    for (int i = pos[l] + 1; i < pos[r]; i++) c = updzen(i, c);
    return updsan(f[pos[r]], r, c);
}
int main() {
    read(n, m), s = sqrt(n);
    for (int i = 1; i <= n; i++)
        read(a[i]), e[pos[i] = (i - 1) / s + 1] = i, val[pos[i]].push(a[i]);
    for (int i = n; i; i--) f[pos[i]] = i;
    while (m--) {
        int l, r, v;
        read(l, r, v);
        if (l <= r)
            println(upd(l, r, v));
        else
            println(upd(1, r, upd(l, n, v)));
    }
    return 0;
}

Luogu P7482 不条理狂诗曲

分治板子题。

时间复杂度 $O(n \log^2 n)$ 。

code

const ll P = 1e9 + 7;
const int N = 1e5 + 10;
int a[N], n;
ll ans = 0;
ll f[N][2], g[N][2];
vector<pair<ll, int> > vec, vec2;
inline void add(ll x) { ans = ans + x; if (ans >= P) ans -= P; }
void solve(int L, int R) {
    if (L == R) return void(add(a[L]));
    int M = L + R >> 1;
    solve(L, M), solve(M + 1, R);
    f[M][0] = 0, f[M][1] = -INF;
    g[M + 1][0] = 0, g[M + 1][1] = -INF;
    f[M + 1][0] = 0, f[M + 1][1] = a[M + 1];
    g[M][0] = 0, g[M][1] = a[M];
    clear(vec), clear(vec2);
    for (int i = M + 2; i <= R; i++) f[i][0] = max(f[i - 1][0], f[i - 2][0] + a[i]), f[i][1] = max(f[i - 2][1] + a[i], f[i - 1][1]);
    for (int i = M - 1; i >= L; i--) g[i][0] = max(g[i + 1][0], g[i + 2][0] + a[i]), g[i][1] = max(g[i + 2][1] + a[i], g[i + 1][1]);
    for (int i = M + 1; i <= R; i++) chkmax(f[i][0], f[i - 1][0]), chkmax(f[i][1], f[i - 1][1]), chkmax(f[i][1], f[i][0]), vec2.emplace_back(f[i][1] - f[i][0], i);
    for (int i = M; i >= L; i--) chkmax(g[i][0], g[i + 1][0]), chkmax(g[i][1], g[i + 1][1]), chkmax(g[i][1], g[i][0]), vec.emplace_back(g[i][1] - g[i][0], i);
    sort(vec.begin(), vec.end(), greater<>()), sort(vec2.begin(), vec2.end(), greater<>());
    int r = 0;
    ll sum = 0;
    for (auto [x, y] : vec) sum += g[y][0];
    for (auto [u, i] : vec2) {
        while (r < vec.size() && vec[r].first >= u) sum = sum - g[vec[r].second][0] + g[vec[r].second][1], r++;
        ans = (ans + r * (f[i][0] % P) + (vec.size() - r) * (f[i][1] % P) + sum) % P;
    }
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    solve(1, n);
    cout << ans;
}

Luogu P4340 SHOI2016 随机序列

我们发现，如果一个数不在开头，那么除了乘号，前面的 $+$ 和 $-$ 会抵消，因此只用对前缀积算贡献。

记录 $s_i$ 为前缀积，记答案为 $2\sum_{i}^{n-1}s_i3^{n-i-1}+s_n$ 。

然后线段树维护即可。

code

const int N = 1e5 + 10;
const ll P = 1e9 + 7;
ll w[N << 2], val[N << 2], pw[N];
int a[N], pos[N], n, m;
inline void setup(int u, int v) {
    w[u] = a[v], val[u] = v == n ? a[v] : (pw[n - v - 1] * a[v] % P);
}
void build(int u, int L, int R) {
    if (L == R) return pos[L] = u, setup(u, L);
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R);
    w[u] = w[u << 1] * w[u << 1 | 1] % P, val[u] = (val[u << 1] + w[u << 1] * val[u << 1 | 1]) % P;
}
inline void update(int u) {
    setup(pos[u], u), u = pos[u];
    while (u >>= 1) w[u] = w[u << 1] * w[u << 1 | 1] % P, val[u] = (val[u << 1] + w[u << 1] * val[u << 1 | 1]) % P;
}
int main() {
    read(n, m), pw[0] = 2;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * 3;
        if (pw[i] >= P) pw[i] -= P;
        if (pw[i] >= P) pw[i] -= P;
    }
    for (int i = 1; i <= n; i++) read(a[i]);
    build(1, 1, n);
    while (m--) {
        int x, v;
        read(x, v), a[x] = v, update(x), println(val[1]);
    }
}

Luogu P7826 「RdOI R3」RBT

我们发现，如果按照 $\text{id}$ 从小到大 $\text{dfs}$ 遍历树，那么操作 $3$ 并不会改变 $\text{dfn}$ 序。

现在问题转化为序列问题，出现奇数次的数可以直接 $\text{bitset}$ 的异或运算算出，然后直接做就行了。

复杂度 $O(np + \dfrac{np\log n}{w})$ 。

code

const int N = 1e5 + 10, T = 512;
const ll P = 998244353;
bitset<512> w[N << 2], g;
int n, m, p, k, fa[N], pw[T], dfn[N], siz[N], a[N], dfncnt, id[N];
vector<int> vec[N];
set<int> s[N];
inline ll qpw(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % P;
        a = a * a % P, b >>= 1;
    }
    return ans;
}
int lzy[N << 2];
inline void maketag(int u, int v) {
    if ((lzy[u] += v) >= p) lzy[u] -= p;
    w[u] = ((w[u] << v) | (w[u] >> (p - v))) & g;
}
inline void pushdown(int u) {
    if (lzy[u])
        maketag(u << 1, lzy[u]), maketag(u << 1 | 1, lzy[u]), lzy[u] = 0;
}
inline bitset<512> query(int u, int L, int R, int l, int r) {
    if (L >= l && R <= r) return w[u];
    pushdown(u);
    int M = L + R >> 1;
    if (r <= M) return query(u << 1, L, M, l, r);
    if (M < l) return query(u << 1 | 1, M + 1, R, l, r);
    return query(u << 1, L, M, l, r) ^ query(u << 1 | 1, M + 1, R, l, r);
}
void update(int u, int L, int R, int l, int r, int v) {
    if (L >= l && R <= r) return maketag(u, v);
    if (L > r || R < l) return;
    int M = L + R >> 1;
    pushdown(u), update(u << 1, L, M, l, r, v);
    update(u << 1 | 1, M + 1, R, l, r, v), w[u] = w[u << 1] ^ w[u << 1 | 1];
}
inline int change(int u, int L, int R, int x, int v) {
    if (L == R) {
        int c = w[u]._Find_first();
        w[u].flip(c), w[u].flip(v);
        return c;
    }
    int M = L + R >> 1, t;
    pushdown(u);
    if (x <= M)
        t = change(u << 1, L, M, x, v);
    else
        t = change(u << 1 | 1, M + 1, R, x, v);
    // w[u] = w[u << 1] ^ w[u << 1 | 1];
    return w[u].flip(t), w[u].flip(v), t;
}
void build(int u, int L, int R) {
    if (L == R) return w[u].set(a[id[L]]), void();
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R),
        w[u] = w[u << 1] ^ w[u << 1 | 1];
}
void dfs(int u) {
    siz[u] = 1, id[dfn[u] = ++dfncnt] = u;
    for (int v : vec[u])
        if (v != fa[u]) fa[v] = u, s[u].insert(v), dfs(v), siz[u] += siz[v];
}
int tw[(T >> 4) + 1][1 << 16];
inline int calc(bitset<512> x) {
    int ans = 0;
    for (int i = 0; i < p; i++)
        if (x.test(i)) {
            if ((ans += pw[i]) >= P) ans -= P;
        }
    return ans;
}
int main() {
    read(n, m, p, k);
    for (int i = 0; i < p; i++) g.set(i), pw[i] = qpw(i, k);
    // for (int i = 0; i <= (p >> 4); i++) {
        
    // }
    for (int i = 1; i <= n; i++) read(a[i]), assert(a[i] < p);
    for (int i = 1, u, v; i < n; i++)
        read(u, v), vec[u].push_back(v), vec[v].push_back(u);
    for (int i = 1; i <= n; i++) sort(vec[i].begin(), vec[i].end());
    dfs(1), build(1, 1, n);
    while (m--) {
        int op, u, b;
        read(op, u);
        if (op == 1) read(b), update(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, b);
        else if (op == 2) read(b), change(1, 1, n, dfn[u], b);
        else if (op == 3) {
            if (!s[fa[u]].size()) continue;
            auto c = s[fa[u]].lower_bound(u);
            if (c == s[fa[u]].begin()) continue;
            siz[*(--c)] += siz[u], s[fa[u]].erase(u);
        } else println(calc(query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1)));
    }
    return 0;
}

CF1083C Max Mex

我们发现，答案等价于询问一个权值上的最长前缀使得对应点在同一条链上。

判断点 $u$ 是否在链 $x, y$ 上可以看 $\text{dist}(u, x) + \text{dist}(u, y)$ 是否为 $\text{dist}(x, y)$ ，然后用线段树维护修改操作，线段树上每个节点存储链的端点以及是否能构成链即可。

时间复杂度： $O(n \log^c n)$ ， $c$ 取决于实现。

code

const int N = 2e5 + 10;
struct Link {
    bool c;
    int u, v;
};
int dep[N];
int top[N], fa[N], siz[N], son[N], n;
vector<int> vec[N];
void dfs(int u) {
    siz[u] = 1;
    for (int v : vec[u]) {
            fa[v] = u, dep[v] = dep[u] + 1, dfs(v), siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) son[u] = v;
        }
}
void dfs2(int u) {
    for (int v : vec[u])
        top[v] = (v == son[u]) ? top[u] : v, dfs2(v);
}
inline int lca(int u, int v) {
    while (top[u] != top[v]) dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
inline int dist(int u, int v) { return dep[u] + dep[v] - (dep[lca(u, v)] << 1);}
inline bool judge(int u, int v, int w) {
    if (u == v || u == w) return 1;
    int d1 = dist(u, v), d2 = dist(u, w), d3 = dist(v, w);
    return (d1 + d2 == d3);
}
inline Link operator+(Link a, Link b) {
    if (!a.c || !b.c) return {};
    int v[4] = {a.u, a.v, b.u, b.v};
    for (int i = 0; i < 4; i++)
        for (int j = i + 1; j < 4; j++) {
            bool fl = 1;
            for (int k = 0; k < 4; k++)
                if (!judge(v[k], v[i], v[j])) {
                    fl = 0;
                    break;
                } 
            if (fl) return {1, v[i], v[j]};
        }
    return {};
}
Link w[N << 2];
int pos[N], a[N], at[N];
void build(int u, int L, int R) {
    if (L == R)
        return at[L] = u, void(w[u] = {1, pos[L], pos[L]});
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R), w[u] = w[u << 1] + w[u << 1 | 1];
    // if (!w[u].c) cout << "findx:" << u  << ' ' << w[u << 1].c << ' ' << w[u << 1 | 1].c << endl;
}
inline void update(int u, Link c) {
    w[u = at[u]] = c;
    while (u >>= 1) w[u] = w[u << 1] + w[u << 1 | 1];
}
inline int query() {
    if (w[1].c) return n;
    int L = 0, u = 1, R = n - 1;
    Link now, cur;
    bool fl = 0;
    while (L < R) {
        int M = L + R >> 1;
        if (!fl)
            cur = w[u << 1];
        else 
            cur = now + w[u << 1];
        if (cur.c) L = M + 1, u = u << 1 | 1, now = cur, fl = 1;
        else R = M, u <<= 1;
    }
    return L;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]), pos[a[i]] = i;
    for (int i = 2, v; i <= n; i++) read(v), vec[v].push_back(i);
    dfs(top[1] = dep[1] = 1), dfs2(1);
    build(1, 0, n - 1);
    int q;
    read(q); while (q--) {
        int op;
        read(op);
        if (op == 2) println(query());
        else {
            int u, v;
            read(u, v);
            swap(a[u], a[v]), update(a[u], {1, u, u}), update(a[v], {1, v, v});
        }
    }
    return 0;
}

Luogu P9531 JOISC2022 复兴计划

简要题意：

给定 $m$ 个三元组 $(u_i,v_i,w_i)$ ，每次询问给出一个 $x$ ，保证询问的 $x$ 单调递增，查询对于所有 $1 \le i \le m$ 在树上连边 $(u_i, v_i, |w_i - x|)$ ，求 $\text{MST}$ 边权和。

结论：一个边在 $\text{MST}$ 中存在时的 $x$ 是一段连续区间。

做法：从大到小枚举边，维护动态树。加入一条边 $(u, v, w)$ 时，如果动态树上两点不联通，则直接加入，找到链上权值最大的边 $(u', v', w')$ ，那么当前这条边存在有条件 $x \le \dfrac {w + w'} 2$ ，另一条边存在有条件 $x > \dfrac {w + w'} 2$ ，然后删去那条边，加入该边即可，该部分可以用 LCT 维护。

这样就可以求出每条边存在时的 $x$ 区间。

最后询问直接双指针就行了，时间复杂度 $O(m (\log n + \log m) + q)$ 。

code

const int N = 2e5 + 10;
int v[N], ch[N][2], fa[N], sum[N];
bool lzy[N];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
inline bool isroot(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
inline void connect(int u, int v, bool k) { ch[u][k] = v, fa[v] = u; }
inline bool get(int u) { return rc(fa[u]) == u; }
inline void pushup(int u) {
    if (u) {
        sum[u] = u;
        if (lc(u) && v[sum[lc(u)]] > v[sum[u]]) sum[u] = sum[lc(u)];
        if (rc(u) && v[sum[rc(u)]] > v[sum[u]]) sum[u] = sum[rc(u)];
    }
}
inline void maketag(int u) { lzy[u] ^= 1, swap(lc(u), rc(u)); }
inline void pushdown(int u) {
    if (lzy[u]) {
        if (lc(u)) maketag(lc(u));
        if (rc(u)) maketag(rc(u));
        lzy[u] = 0;
    }
}
inline void update(int u) {
    if (!isroot(u)) update(fa[u]);
    pushdown(u);
}
inline void rotate(int u) {
    bool k = get(u), kf = get(fa[u]);
    int f = fa[u];
    if (isroot(f))
        fa[u] = fa[f];
    else
        connect(fa[f], u, kf);
    connect(f, ch[u][k ^ 1], k), connect(u, f, k ^ 1);
    pushup(f), pushup(u);
}
inline void splay(int u) {
    update(u);
    for (int f = fa[u]; f = fa[u], !isroot(u); rotate(u))
        if (!isroot(f)) rotate(get(u) == get(f) ? f : u);
}
inline void access(int u) {
    for (int f = 0; u; u = fa[f = u]) splay(u), rc(u) = f, pushup(u);
}
inline void makeroot(int u) { access(u), splay(u), maketag(u); }
inline void split(int u, int v) { makeroot(u), access(v), splay(v); }
inline int find(int u) {
    access(u), splay(u), pushdown(u);
    while (lc(u)) pushdown(u = lc(u));
    return splay(u), u;
}
inline void link(int u, int v) {
    makeroot(u), fa[u] = v;
}
inline void cut(int u, int v) {
    split(u, v);
    if (lc(v) == u && !rc(u)) lc(v) = fa[u] = 0, pushup(v);
}
int n, m;
struct Edge {
    int u, v, w;
    inline bool operator<(Edge b) const { return w > b.w; }
} e[N];
pair<ll, pair<ll, int> > vec[N * 3];
int L[N], R[N],top;
int main() {
    read(n, m);
    memset(L, -0x3f, sizeof(L)), memset(R, 0x3f, sizeof(R));
    for (int i = 1; i <= m; i++) read(e[i].u, e[i].v, e[i].w);
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; i++) v[i + n] = e[i].w;
    for (int i = 1; i <= n + m; i++) pushup(i);
    for (int i = 1; i <= m; i++) {
        if (find(e[i].u) == find(e[i].v)) {
            split(e[i].u, e[i].v);
            int c = sum[e[i].v] - n;
            cut(e[c].u, c + n);
            int M = e[c].w + e[i].w >> 1;
            R[i] = M, L[c] = M + 1;
        }
        link(e[i].u, i + n), link(i + n, e[i].v);
    }
    for (int i = 1; i <= m; i++) {
        vec[++top] = {L[i], {e[i].w, -1}};
        vec[++top] = {e[i].w, {-e[i].w * 2, 2}};
        vec[++top] = {R[i] + 1, {e[i].w, -1}};
    }
    sort(vec + 1, vec + top + 1);
    ll ans = 0;
    int q, x, r = 0;
    read(q);
    ll sum = 0, tot = 0;
    while (q--) {
        read(x);
        while (r <= top && vec[r].first <= x)
            sum += vec[r].second.first, tot += vec[r].second.second, ++r; 
        println(sum + tot * x);
    }
    return 0;
}